DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.54

New Approximation Algorithms for Touring Regions

Authors: Benjamin Qi and Richard Qi

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, … , R_n in that order. Our main result is an O (n/√ε log{1/ε} + 1/ε)-time algorithm for touring disjoint disks. We also give an O(min(n/ε, n²/√ε))-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O(n/{ε^{d-1}} log²1/ε + 1/ε^{2d-2}) and O(n/ε^{2d-2})-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.

Cite as

Benjamin Qi and Richard Qi. New Approximation Algorithms for Touring Regions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{qi_et_al:LIPIcs.SoCG.2023.54,
  author =	{Qi, Benjamin and Qi, Richard},
  title =	{{New Approximation Algorithms for Touring Regions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.54},
  URN =		{urn:nbn:de:0030-drops-179047},
  doi =		{10.4230/LIPIcs.SoCG.2023.54},
  annote =	{Keywords: shortest paths, convex bodies, fat objects, disks}
}

Search Results

Documents authored by Qi, Richard

New Approximation Algorithms for Touring Regions

Abstract

Cite as

Thanks for your feedback!

Could not send message